{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Number of Operations to Make Arrays Similar"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: makeSimilar"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #使数组相似的最少操作次数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个正整数数组&nbsp;<code>nums</code> 和&nbsp;<code>target</code>&nbsp;，两个数组长度相等。</p>\n",
    "\n",
    "<p>在一次操作中，你可以选择两个 <strong>不同</strong>&nbsp;的下标&nbsp;<code>i</code> 和&nbsp;<code>j</code>&nbsp;，其中&nbsp;<code>0 &lt;= i, j &lt; nums.length</code>&nbsp;，并且：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>令&nbsp;<code>nums[i] = nums[i] + 2</code>&nbsp;且</li>\n",
    "\t<li>令&nbsp;<code>nums[j] = nums[j] - 2</code>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>如果两个数组中每个元素出现的频率相等，我们称两个数组是 <strong>相似</strong>&nbsp;的。</p>\n",
    "\n",
    "<p>请你返回将 <code>nums</code>&nbsp;变得与 <code>target</code>&nbsp;相似的最少操作次数。测试数据保证 <code>nums</code>&nbsp;一定能变得与 <code>target</code>&nbsp;相似。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [8,12,6], target = [2,14,10]\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>可以用两步操作将 nums 变得与 target 相似：\n",
    "- 选择 i = 0 和 j = 2 ，nums = [10,12,4] 。\n",
    "- 选择 i = 1 和 j = 2 ，nums = [10,14,2] 。\n",
    "2 次操作是最少需要的操作次数。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [1,2,5], target = [4,1,3]\n",
    "<b>输出：</b>1\n",
    "<b>解释：</b>一步操作可以使 nums 变得与 target 相似：\n",
    "- 选择 i = 1 和 j = 2 ，nums = [1,4,3] 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [1,1,1,1,1], target = [1,1,1,1,1]\n",
    "<b>输出：</b>0\n",
    "<b>解释：</b>数组 nums 已经与 target 相似。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == nums.length == target.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i], target[i] &lt;= 10<sup>6</sup></code></li>\n",
    "\t<li><code>nums</code>&nbsp;一定可以变得与&nbsp;<code>target</code> 相似。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-number-of-operations-to-make-arrays-similar](https://leetcode.cn/problems/minimum-number-of-operations-to-make-arrays-similar/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-number-of-operations-to-make-arrays-similar](https://leetcode.cn/problems/minimum-number-of-operations-to-make-arrays-similar/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[8,12,6]\\n[2,14,10]', '[1,2,5]\\n[4,1,3]', '[1,1,1,1,1]\\n[1,1,1,1,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def f(a: List[int]) -> None:\n",
    "    for i, x in enumerate(a):\n",
    "        if x % 2: a[i] = -x  # 由于元素都是正数，把奇数变成相反数，这样排序后奇偶就自动分开了\n",
    "    a.sort()\n",
    "\n",
    "class Solution:\n",
    "    def makeSimilar(self, nums: List[int], target: List[int]) -> int:\n",
    "        f(nums)\n",
    "        f(target)\n",
    "        return sum(abs(x - y) for x, y in zip(nums, target)) // 4\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSimilar(self, nums: List[int], target: List[int]) -> int:\n",
    "        odd_nums  = sorted([x for x in nums if x % 2 == 1])\n",
    "        even_nums = sorted([x for x in nums if x % 2 == 0])\n",
    "        odd_tar  = sorted([x for x in target if x % 2 == 1])\n",
    "        even_tar = sorted([x for x in target if x % 2 == 0])\n",
    "        ans = 0;\n",
    "        for x, y in zip(odd_nums, odd_tar):\n",
    "            ans += abs(x - y)\n",
    "        for x, y in zip(even_nums, even_tar):\n",
    "            ans += abs(x - y)\n",
    "        return ans // 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSimilar(self, nums: List[int], target: List[int]) -> int:\n",
    "        oddn,evenn=[],[]\n",
    "        oddt,event=[],[]\n",
    "        for n,t in zip(nums,target):\n",
    "            if n%2:\n",
    "                oddn.append(n)\n",
    "            else:\n",
    "                evenn.append(n)\n",
    "            if t%2:\n",
    "                oddt.append(t)\n",
    "            else:\n",
    "                event.append(t)\n",
    "        oddn.sort()\n",
    "        oddt.sort()\n",
    "        evenn.sort()\n",
    "        event.sort()\n",
    "        #print(oddn,oddt)\n",
    "        #print(evenn,event)\n",
    "        ret=0\n",
    "        temp=0\n",
    "        for n,t in zip(oddn,oddt):\n",
    "            ret+=abs(n-t)\n",
    "        for n,t in zip(evenn,event):\n",
    "            ret+=abs(n-t)\n",
    "        ret//=4\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSimilar(self, nums: List[int], target: List[int]) -> int:\n",
    "        # nums.sort()\n",
    "        # target.sort()\n",
    "        # for x in nums:\n",
    "\n",
    "\n",
    "        # counter1, counter2 = Counter(nums), Counter(target)\n",
    "        # more = 0\n",
    "        # for x in counter1.keys():\n",
    "        #     if counter1[x] >= counter2[x]:\n",
    "        #         more += (counter1[x] - counter2[x])\n",
    "\n",
    "\n",
    "        n1 = sorted(x for x in nums if x & 1) + sorted(x for x in nums if x & 1 == 0)\n",
    "        t1 = sorted(x for x in target if x & 1) + sorted(x for x in target if x & 1 == 0)\n",
    "        ans = 0\n",
    "        for i, x in enumerate(n1):\n",
    "            ans += abs(x - t1[i])\n",
    "        return ans // 4\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSimilar(self, nums: List[int], target: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        odd, even = [], []\n",
    "        odd2, even2 = [], []\n",
    "        for i in range(n):\n",
    "            if nums[i] % 2:\n",
    "                odd.append(nums[i])\n",
    "            else:\n",
    "                even.append(nums[i])\n",
    "            if target[i] % 2:\n",
    "                odd2.append(target[i])\n",
    "            else:\n",
    "                even2.append(target[i])\n",
    "        odd.sort()\n",
    "        even.sort()\n",
    "        odd2.sort()\n",
    "        even2.sort()\n",
    "        res = 0\n",
    "        for i in range(len(odd)):\n",
    "            if odd[i] > odd2[i]:\n",
    "                res += odd[i] - odd2[i]\n",
    "        for i in range(len(even)):\n",
    "            if even[i] > even2[i]:\n",
    "                res += even[i] - even2[i]\n",
    "        return res // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSimilar(self, nums: List[int], target: List[int]) -> int:\n",
    "        def calc(l, r):\n",
    "            l.sort()\n",
    "            r.sort()\n",
    "            ret = 0\n",
    "            for vl, vr in zip(l, r):\n",
    "                ret += abs(vl - vr) // 2\n",
    "            return ret\n",
    "        \n",
    "        ljs = [n for n in nums if n % 2]\n",
    "        rjs = [n for n in target if n % 2]\n",
    "        les = [n for n in nums if n % 2 == 0]\n",
    "        res = [n for n in target if n % 2 == 0]\n",
    "\n",
    "        return (calc(ljs, rjs) + calc(les, res)) // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSimilar(self, nums: List[int], target: List[int]) -> int:\n",
    "        numsOdd, numsEven, targetOdd, targetEven = sorted([x for x in nums if x % 2]), sorted([x for x in nums if x % 2 == 0]), sorted([x for x in target if x % 2]), sorted([x for x in target if x % 2 == 0])\n",
    "        return sum(max(numsOdd[i] - targetOdd[i], 0) // 2 for i in range(len(numsOdd))) + sum(max(numsEven[i] - targetEven[i], 0) // 2 for i in range(len(numsEven)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def f(a: List[int]) -> None:\n",
    "    for i, x in enumerate(a):\n",
    "        if x % 2: a[i] = -x  # 由于元素都是正数，把奇数变成相反数，这样排序后奇偶就自动分开了\n",
    "    a.sort()\n",
    "\n",
    "class Solution:\n",
    "    def makeSimilar(self, nums: List[int], target: List[int]) -> int:\n",
    "        f(nums)\n",
    "        f(target)\n",
    "        return sum(abs(x - y) for x, y in zip(nums, target)) // 4\n",
    "\n",
    "# 作者：灵茶山艾府\n",
    "# 链接：https://leetcode.cn/problems/minimum-number-of-operations-to-make-arrays-similar/solutions/1917413/by-endlesscheng-lusx/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def makeSimilar(self, nums: List[int], target: List[int]) -> int:\n",
    "        nums = sorted(map(lambda x: -x if x & 1 else x, nums))\n",
    "        target = sorted(map(lambda x: -x if x & 1 else x, target))\n",
    "\n",
    "        ans = 0\n",
    "        for x, y in zip(nums, target):\n",
    "            ans += abs(x - y)\n",
    "        return ans >> 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSimilar(self, nums: List[int], target: List[int]) -> int:\n",
    "\n",
    "        odd = [num for num in nums if num % 2]\n",
    "        even = [num for num in nums if num % 2 == 0]\n",
    "        target_odd = [num for num in target if num % 2]\n",
    "        target_even = [num for num in target if num % 2==0]\n",
    "\n",
    "        odd.sort()\n",
    "        target_odd.sort()\n",
    "        ans = 0\n",
    "        for i in range(len(odd)):\n",
    "            x, y = odd[i], target_odd[i]\n",
    "            if x > y:\n",
    "                ans += (x-y)//2\n",
    "        even.sort()\n",
    "        target_even.sort()\n",
    "        for i in range(len(even)):\n",
    "            x, y = even[i], target_even[i]\n",
    "            if x > y:\n",
    "                ans += (x - y) // 2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSimilar(self, nums: List[int], target: List[int]) -> int:\n",
    "        a = [i for i in nums if i%2==0]\n",
    "        b = [i for i in nums if i%2==1]\n",
    "        c = [i for i in target if i%2==0]\n",
    "        d = [i for i in target if i%2==1]\n",
    "        a.sort()\n",
    "        b.sort()\n",
    "        c.sort()\n",
    "        d.sort()\n",
    "        div1 = [i-j for i,j in zip(a,c)  if i-j > 0]\n",
    "        div2 = [i-j for i,j in zip(b,d)  if i-j > 0]\n",
    "        return sum(div1)//2 + sum(div2)//2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def f(a: List[int]) -> None:\n",
    "    for i, x in enumerate(a):\n",
    "        if x % 2: a[i] = -x  # 由于元素都是正数，把奇数变成相反数，这样排序后奇偶就自动分开了\n",
    "    a.sort()\n",
    "\n",
    "class Solution:\n",
    "    def makeSimilar(self, nums: List[int], target: List[int]) -> int:\n",
    "        f(nums)\n",
    "        f(target)\n",
    "        return sum(abs(x - y) for x, y in zip(nums, target)) // 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def f(a: List[int]) -> None:\n",
    "    for i, x in enumerate(a):\n",
    "        if x % 2: a[i] = -x  # 由于元素都是正数，把奇数变成相反数，这样排序后奇偶就自动分开了\n",
    "    a.sort()\n",
    "\n",
    "class Solution:\n",
    "    def makeSimilar(self, nums: List[int], target: List[int]) -> int:\n",
    "        f(nums)\n",
    "        f(target)\n",
    "        return sum(abs(x - y) for x, y in zip(nums, target)) // 4\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "def f(a: List[int]) -> None:\n",
    "    for i, x in enumerate(a):\n",
    "        if x % 2: a[i] = -x  # 由于元素都是正数，把奇数变成相反数，这样排序后奇偶就自动分开了\n",
    "    a.sort()\n",
    "\n",
    "class Solution:\n",
    "    def makeSimilar(self, nums: List[int], target: List[int]) -> int:\n",
    "        f(nums)\n",
    "        f(target)\n",
    "        \n",
    "        # 计算排序后的数组之间每一对相应位置的元素差的绝对值之和，再除以4（因为每次操作会改变两个元素，一个增加2，一个减少2）\n",
    "        return sum(abs(x - y) for x, y in zip(nums, target)) // 4\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def f(a: List[int]) -> None:\n",
    "    for i, x in enumerate(a):\n",
    "        if x % 2: a[i] = -x  # 由于元素都是正数，把奇数变成相反数，这样排序后奇偶就自动分开了\n",
    "    a.sort()\n",
    "\n",
    "class Solution:\n",
    "    def makeSimilar(self, nums: List[int], target: List[int]) -> int:\n",
    "        f(nums)\n",
    "        f(target)\n",
    "        return sum(abs(x - y) for x, y in zip(nums, target)) // 4\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSimilar(self, nums: List[int], target: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        target.sort()\n",
    "        isOdd = lambda n: n & 1\n",
    "        isEven = lambda n: n & 1 == 0\n",
    "        return sum(abs(n1-n2) for n1, n2 in chain(zip(filter(isOdd, nums), filter(isOdd, target)), zip(filter(isEven, nums), filter(isEven, target)))) >> 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSimilar(self, nums: list[int], target: list[int]) -> int:\n",
    "        odd = sorted([num  for num in nums if num %2 ==0])\n",
    "        even = sorted([num  for num in nums if num %2 ==1])\n",
    "        oddtarget = sorted([num  for num in target if num %2 ==0])\n",
    "        eventarget  = sorted([num  for num in target if num %2 ==1])\n",
    "        plus=0\n",
    "        minus=0\n",
    "        for i in range(len(odd)):\n",
    "            if oddtarget[i]-odd[i]>0:\n",
    "                plus += (oddtarget[i]-odd[i])//2\n",
    "            else:\n",
    "                minus += -(oddtarget[i]-odd[i])//2\n",
    "        for i in range(len(even)):\n",
    "            if eventarget[i]-even[i]>0:\n",
    "                plus += (eventarget[i]-even[i])//2\n",
    "            else:\n",
    "                minus += -(eventarget[i]-even[i])//2\n",
    "        return plus"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def f(a: List[int]) -> None:\n",
    "    for i, x in enumerate(a):\n",
    "        if x % 2: a[i] = -x  # 由于元素都是正数，把奇数变成相反数，这样排序后奇偶就自动分开了\n",
    "    a.sort()\n",
    "\n",
    "class Solution:\n",
    "    def makeSimilar(self, nums: List[int], target: List[int]) -> int:\n",
    "        f(nums)\n",
    "        f(target)\n",
    "        return sum(abs(x - y) for x, y in zip(nums, target)) // 4\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def f(nums: List[int]) -> None:\n",
    "        for i, x in enumerate(nums):\n",
    "            if x % 2 == 1 :\n",
    "                nums[i] = -nums[i]\n",
    "        nums.sort()\n",
    "class Solution:\n",
    "    def makeSimilar(self, nums: List[int], target: List[int]) -> int:\n",
    "        f(nums)\n",
    "        f(target)\n",
    "        return sum(abs(x-y) for x, y in zip(nums, target)) //4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSimilar(self, nums: List[int], target: List[int]) -> int:\n",
    "        oddnums=[]\n",
    "        evennums=[]\n",
    "        oddtarget=[]\n",
    "        eventarget=[]\n",
    "        for i in nums:\n",
    "            if i%2==0:\n",
    "                evennums.append(i)\n",
    "            else:\n",
    "                oddnums.append(i)\n",
    "        for i in target:\n",
    "            if i%2==0:\n",
    "                eventarget.append(i)\n",
    "            else:\n",
    "                oddtarget.append(i)\n",
    "        evennums.sort()\n",
    "        oddnums.sort()\n",
    "        eventarget.sort()\n",
    "        oddtarget.sort()\n",
    "        s=0\n",
    "        for i in range(len(evennums)):\n",
    "            s+=abs(eventarget[i]-evennums[i])//2\n",
    "        for i in range(len(oddnums)):\n",
    "            s+=abs(oddtarget[i]-oddnums[i])//2\n",
    "        return s//2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSimilar(self, nums: List[int], target: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        target.sort()\n",
    "        nums_1 = [x for x in nums if x % 2]\n",
    "        nums_2 = [x for x in nums if x % 2 == 0]\n",
    "        tar_1 = [x for x in target if x % 2]\n",
    "        tar_2 = [x for x in target if x % 2 == 0]\n",
    "        ans = 0\n",
    "        for x, y in zip(nums_1, tar_1):\n",
    "            if x == y:\n",
    "                continue\n",
    "            res = x - y\n",
    "            if res > 0:\n",
    "                ans += res // 2\n",
    "        for x, y in zip(nums_2, tar_2):\n",
    "            if x == y:\n",
    "                continue\n",
    "            res = x - y\n",
    "            if res > 0:\n",
    "                ans += res // 2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 按奇偶性分类贪心\n",
    "# 由于操作不会修改元素的奇偶性，所以需要区分奇偶来操作，而题目保证可以使数组相似，所以贪心地令最小的、次小的、第三小的...一对元素相似（可以用邻项交换法证明），就可以使得代价最小。\n",
    "# 具体代码实现时，由于每个数都是正数，区分奇偶性可以将奇数修改为负数，然后计算所有数对代价后除以4就是答案。\n",
    "class Solution:\n",
    "    def makeSimilar(self, nums: List[int], target: List[int]) -> int:\n",
    "        return sum(abs(x - y) for x, y in zip(sorted([-x if x & 1 else x for x in nums]), sorted(\n",
    "            [-y if y & 1 else y for y in target]))) >> 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque, defaultdict, Counter\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def makeSimilar(self, nums: List[int], target: List[int]) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param nums:\n",
    "        :param target:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "\n",
    "        ll2_odd = []\n",
    "        ll2_even = []\n",
    "        for i in target:\n",
    "            if i % 2 == 0:\n",
    "                ll2_even.append(i)\n",
    "            else:\n",
    "                ll2_odd.append(i)\n",
    "        ll2_even.sort(key=lambda x: x)\n",
    "        ll2_odd.sort(key=lambda x: x)\n",
    "\n",
    "        ll1_odd = []\n",
    "        ll1_even = []\n",
    "        for i in nums:\n",
    "            if i % 2 == 0:\n",
    "                ll1_even.append(i)\n",
    "            else:\n",
    "                ll1_odd.append(i)\n",
    "        ll1_even.sort(key=lambda x: x)\n",
    "        ll1_odd.sort(key=lambda x: x)\n",
    "\n",
    "\n",
    "        cnt = 0\n",
    "        for i in zip(ll1_odd, ll2_odd):\n",
    "            cnt += abs(i[0] - i[1])\n",
    "        for i in zip(ll1_even, ll2_even):\n",
    "            cnt += abs(i[0] - i[1])\n",
    "        return cnt // 4\n",
    "\n",
    "\n",
    "a = Solution()\n",
    "print(a.makeSimilar(nums = [8,12,6], target = [2,14,10]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSimilar(self, nums: List[int], target: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        target.sort()\n",
    "        ans = 0\n",
    "        n1 = []\n",
    "        n2 = []\n",
    "        t1 = []\n",
    "        t2 = []\n",
    "        for nn,tt in zip(nums,target):\n",
    "            if nn%2==0:\n",
    "                n2.append(nn)\n",
    "            else:\n",
    "                n1.append(nn)\n",
    "            if tt%2==0:\n",
    "                t2.append(tt)\n",
    "            else:\n",
    "                t1.append(tt)\n",
    "        for nn,tt in zip(n1,t1):\n",
    "            ans+=abs(nn-tt)/4\n",
    "        for nn,tt in zip(n2,t2):\n",
    "            ans+=abs(nn-tt)/4\n",
    "        return int(ans)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from itertools import *\n",
    "from bisect import bisect_left\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def makeSimilar(self, nums: List[int], target: List[int]) -> int:\n",
    "        def f(nums: List[int], target: List[int]):\n",
    "            nums.sort()\n",
    "            target.sort()\n",
    "            res = 0\n",
    "            for a, b in zip(nums, target):\n",
    "                if a > b:\n",
    "                    res += (a - b) // 2\n",
    "            return res\n",
    "        \n",
    "        a = []\n",
    "        b = []\n",
    "        c = []\n",
    "        d = []\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i] & 1:\n",
    "                a.append(nums[i])\n",
    "            else:\n",
    "                c.append(nums[i])\n",
    "            if target[i] & 1:\n",
    "                b.append(target[i])\n",
    "            else:\n",
    "                d.append(target[i])\n",
    "        ans = f(a, b) + f(c, d)\n",
    "        return ans\n",
    "        \n",
    "# end-------------------------------------------------------\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSimilar(self, nums: List[int], target: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort(key=lambda it: [it%2, it])\n",
    "        target.sort(key=lambda it: [it%2, it])\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            x = nums[i] - target[i]\n",
    "            if x > 0:\n",
    "                ans += x//2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSimilar(self, nums: List[int], target: List[int]) -> int:\n",
    "        \n",
    "        nums.sort(key=lambda x: (x % 2, x))\n",
    "        target.sort(key=lambda x: (x % 2, x))\n",
    "        diff = 0\n",
    "        for a, b in zip(nums, target):\n",
    "            diff += abs(a - b)\n",
    "        return diff // 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSimilar(self, nums: List[int], target: List[int]) -> int:\n",
    "        nums.sort(key=lambda x : (x % 2, x))\n",
    "        target.sort(key=lambda x : (x % 2, x))\n",
    "        return sum(nums[i] - target[i] for i in range(len(nums)) if nums[i] > target[i]) // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSimilar(self, nums: List[int], target: List[int]) -> int:\n",
    "        nums.sort(key=lambda x : (x % 2, x))\n",
    "        target.sort(key=lambda x : (x % 2, x))\n",
    "        return sum(a - b for (a, b) in zip(nums, target) if a > b) // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSimilar(self, nums: List[int], target: List[int]) -> int:\n",
    "        nums.sort(key=lambda x : (x % 2, x))\n",
    "        target.sort(key=lambda x : (x % 2, x))\n",
    "        return sum(a - b for (a, b) in zip(nums, target) if a > b) // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSimilar(self, nums: List[int], target: List[int]) -> int:\n",
    "        nums.sort(key=lambda x: (x % 2, x))\n",
    "        target.sort(key=lambda x: (x % 2, x))\n",
    "        return sum(abs(x - target[i]) for i, x in enumerate(nums)) // 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSimilar(self, nums: List[int], target: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        nums.sort(key = lambda x: (x % 2, x))\n",
    "        target.sort(key = lambda x: (x % 2, x))\n",
    "        for num, tg in zip(nums, target):\n",
    "            if num < tg:\n",
    "                res += (tg - num) // 2 \n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSimilar(self, nums: List[int], target: List[int]) -> int:\n",
    "        nums.sort(key=lambda x:(x%2,x))\n",
    "        target.sort(key=lambda x:(x%2,x))\n",
    "\n",
    "        return sum(abs(x-y) for x,y in zip(nums,target))//4\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSimilar(self, A: List[int], B: List[int], K=lambda t: (t & 1, t)) -> int:\n",
    "        return sum(map(lambda t: abs(sub(*t)), zip(sorted(A, key=K), sorted(B, key=K)))) >> 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSimilar(self, nums: List[int], target: List[int]) -> int:\n",
    "        newNums = nums[:]\n",
    "        newTarget = target[:]\n",
    "        newNums.sort(key=lambda x:(x%2,x))\n",
    "        newTarget.sort(key=lambda x:(x%2,x))\n",
    "\n",
    "        return sum(abs(x-y) for x,y in zip(newNums,newTarget))//4\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
